'''
https://leetcode.cn/problems/is-graph-bipartite/description/?envType=study-plan-v2&envId=graph-theory
'''
from typing import List


class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        n = len(graph)
        color = [-1] * n
        def paint(u, c):
            if color[u] != -1:
                return color[u] == c
            color[u] = c
            for v in graph[u]:
                if not paint(v, 1 - c):
                    return False
            return True

        # 题目不保证连通图
        for u in range(n):
            if color[u] == -1:
                if not paint(u, 0):
                    return False
        return True